home *** CD-ROM | disk | FTP | other *** search
/ HPAVC / HPAVC CD-ROM.iso / SNNSV32.ZIP / SNNSv3.2 / kernel / sources / kr_JordElm.c < prev    next >
C/C++ Source or Header  |  1994-04-25  |  14KB  |  497 lines
  1. /*****************************************************************************
  2.   FILE           : kr_JordElm.c
  3.   SHORTNAME      : kr_JordElm.c
  4.   SNNS VERSION   : 3.2
  5.  
  6.   PURPOSE        : Topological sorting for Jordan and Elman networks 
  7.   NOTES          :
  8.  
  9.   AUTHOR         : Tobias Soyez
  10.   DATE           : 09.11.1993
  11.  
  12.   CHANGED BY     : 
  13.   IDENTIFICATION : @(#)kr_JordElm.c    1.2 3/15/94
  14.   SCCS VERSION   : 1.2
  15.   LAST CHANGE    : 3/15/94
  16.  
  17.              Copyright (c) 1990-1994  SNNS Group, IPVR, Univ. Stuttgart, FRG
  18. ******************************************************************************/
  19.  
  20.  
  21. #include "kr_typ.h"    
  22. #include "kr_const.h"     
  23. #include "kr_def.h"     
  24. #include "kr_mac.h"
  25. #include "kernel.h"
  26. #include "kr_JordElm.ph"
  27.  
  28.  
  29.  
  30. /*****************************************************************************
  31.   FUNCTION : kr_recTouchContextUnits
  32.  
  33.   PURPOSE  : touches only context units recursively
  34.   NOTES    : 
  35.  
  36.   RETURNS  : 
  37.   UPDATE   : 
  38. ******************************************************************************/
  39.  
  40. static void kr_recTouchContextUnits (struct Unit *unit_ptr)
  41.  
  42. {
  43.   struct Site   *site_ptr ;
  44.   struct Link   *link_ptr ;
  45.   bool           unit_has_incoming_links ;
  46.  
  47.   if (unit_ptr->flags & UFLAG_REFRESH) return ;
  48.  
  49.   if ((IS_HIDDEN_UNIT (unit_ptr)) && (IS_SPECIAL_UNIT (unit_ptr)))
  50.   {
  51.     /* -----------  touch only context units ------------- */
  52.  
  53.     unit_ptr->flags |= UFLAG_REFRESH ;             /* set the 'touch' flag  */
  54.  
  55.     unit_has_incoming_links = FALSE ;
  56.  
  57.     switch (unit_ptr->flags & UFLAG_INPUT_PAT)
  58.     {
  59.       case  UFLAG_DLINKS:                          /* unit has direct links  */
  60.         FOR_ALL_LINKS (unit_ptr, link_ptr)
  61.     { 
  62.           kr_recTouchContextUnits (link_ptr->to) ; 
  63.           unit_has_incoming_links = TRUE ;
  64.         }
  65.         break ;
  66.  
  67.       case  UFLAG_SITES:                             /*  unit has sites  */
  68.         FOR_ALL_SITES_AND_LINKS (unit_ptr, site_ptr, link_ptr)
  69.     {
  70.       kr_recTouchContextUnits (link_ptr->to) ; 
  71.           unit_has_incoming_links = TRUE ;
  72.         }
  73.         break ;
  74.     }
  75.   }
  76.  
  77.   if ((! unit_has_incoming_links) && (! IS_INPUT_UNIT (unit_ptr)))
  78.   {
  79.     /* unit has no incoming links -> dead unit -> delete touch flag */
  80.  
  81.     unit_ptr->flags &= ~UFLAG_REFRESH ;
  82.   }
  83. }
  84.  
  85.  
  86.  
  87. /*****************************************************************************
  88.   FUNCTION : kr_recTopoCheckJE
  89.  
  90.   PURPOSE  : recursive topology check, called by kr_topoCheckJE
  91.   NOTES    : 
  92.  
  93.   RETURNS  : 
  94.   UPDATE   : 
  95. ******************************************************************************/
  96.  
  97. static void  kr_recTopoCheckJE (struct Unit *unit_ptr, int depth)
  98.  
  99. {
  100.   struct Site   *site_ptr ;
  101.   struct Link   *link_ptr ;
  102.   bool           unit_has_incoming_links ;
  103.  
  104.  
  105.  
  106.   if ((IS_HIDDEN_UNIT (unit_ptr)) && (IS_SPECIAL_UNIT (unit_ptr))) 
  107.   {
  108.     /* --------  touch context units recursively  -------- */
  109.  
  110.     kr_recTouchContextUnits (unit_ptr) ;
  111.     return ;
  112.   }
  113.  
  114.   if (unit_ptr->flags & UFLAG_REFRESH)
  115.   {  
  116.     if (unit_ptr->lln == 0)
  117.     {  
  118.       /*  logical layer no. isn't set => Cycle found  */
  119.       topo_msg.no_of_cycles++ ;
  120.       
  121.       if (topo_msg.error_code == KRERR_NO_ERROR)
  122.       { 
  123.         topo_msg.src_error_unit = unit_ptr - unit_array ;
  124.         topo_msg.error_code     = KRERR_CYCLES ;
  125.       }
  126.     }
  127.     return ;
  128.   }
  129.  
  130.  
  131.   /* -----  unit is not a context unit and has not been touched yet  ------ */
  132.   /* -----  continue recursive depth search                          ------ */
  133.  
  134.   unit_ptr->flags |= UFLAG_REFRESH ;             /* set the 'touch' flag  */
  135.  
  136.   unit_has_incoming_links = FALSE ;
  137.  
  138.   switch (unit_ptr->flags & UFLAG_INPUT_PAT)
  139.   {
  140.     case  UFLAG_DLINKS:                          /* unit has direct links  */
  141.       FOR_ALL_LINKS (unit_ptr, link_ptr)
  142.       {
  143.     kr_recTopoCheckJE (link_ptr->to, depth + 1) ; 
  144.         unit_has_incoming_links = TRUE ;
  145.       }
  146.       break ;
  147.  
  148.     case  UFLAG_SITES:                             /*  unit has sites  */
  149.       FOR_ALL_SITES_AND_LINKS (unit_ptr, site_ptr, link_ptr)
  150.       {
  151.     kr_recTopoCheckJE (link_ptr->to, depth + 1) ; 
  152.         unit_has_incoming_links = TRUE ;
  153.       }
  154.       break ;
  155.   }
  156.  
  157.   /*  remember the depth (for cycle detection and statistics)  */
  158.   unit_ptr->lln = depth ;
  159.  
  160.   /*  store highest layer no.  */
  161.   if (depth > topo_msg.no_of_layers) topo_msg.no_of_layers = depth ;
  162.  
  163.  
  164.   if ((! unit_has_incoming_links) && (! IS_INPUT_UNIT (unit_ptr)))
  165.   {
  166.     /* unit has no incoming links -> dead unit -> delete touch flag */
  167.  
  168.     unit_ptr->flags &= ~UFLAG_REFRESH ;
  169.   }
  170. }
  171.  
  172.  
  173.  
  174. /*****************************************************************************
  175.   FUNCTION : kr_topoCheckJE
  176.  
  177.   PURPOSE  : Checks the topology of partial recurrent networks 
  178.              (i.e. JORDAN or ELMAN networks) :
  179.          only recurrent links to context units are allowed
  180.   NOTES    : 
  181.  
  182.   RETURNS  : kernel error code
  183.   UPDATE   : 
  184. ******************************************************************************/
  185.  
  186. krui_err kr_topoCheckJE (void)
  187.  
  188. {
  189.   struct Unit  *unit_ptr ;
  190.   bool          o_units  ;
  191.  
  192.  
  193.   topo_msg.no_of_cycles     = 
  194.   topo_msg.no_of_dead_units =
  195.   topo_msg.dest_error_unit  = 
  196.   topo_msg.src_error_unit   =
  197.   topo_msg.no_of_layers     = 0 ;
  198.   topo_msg.error_code       = KernelErrorCode = KRERR_NO_ERROR ;
  199.  
  200.  
  201.   if (NoOfUnits == 0)
  202.   {
  203.     /*  no units defined  */
  204.     KernelErrorCode = KRERR_NO_UNITS ;
  205.     return (KernelErrorCode) ;
  206.   }
  207.  
  208.  
  209.   /* -------------------  reset units 'touch' flags  ----------------------- */
  210.  
  211.   FOR_ALL_UNITS (unit_ptr)
  212.     if (UNIT_IN_USE (unit_ptr))
  213.     {
  214.       unit_ptr->flags &= ~UFLAG_REFRESH ;
  215.       unit_ptr->lln = 0 ;
  216.     }
  217.  
  218.  
  219.   /* ----------  begin depth search at the first output unit  -------------- */
  220.  
  221.   o_units = FALSE ;
  222.   FOR_ALL_UNITS (unit_ptr)
  223.     if (IS_OUTPUT_UNIT (unit_ptr) && UNIT_IN_USE (unit_ptr))
  224.     {
  225.       o_units = TRUE ;
  226.       kr_recTopoCheckJE (unit_ptr, 1) ;
  227.       if (topo_msg.error_code != KRERR_NO_ERROR)
  228.       {  /*  stop if an error occured  */
  229.         KernelErrorCode = topo_msg.error_code ;
  230.         return (KernelErrorCode) ;
  231.       }
  232.     }
  233.       
  234.   if (!o_units)
  235.   {  /*  no output units */
  236.     KernelErrorCode = KRERR_NO_OUTPUT_UNITS ;
  237.     return (KernelErrorCode) ;
  238.   }
  239.  
  240.  
  241.   /* ----------  search for dead units i.e. units without inputs  ---------- */
  242.  
  243.   FOR_ALL_UNITS (unit_ptr)
  244.     if (!(unit_ptr->flags & UFLAG_REFRESH) && UNIT_IN_USE (unit_ptr))
  245.     {
  246.       topo_msg.error_code = KRERR_DEAD_UNITS ;
  247.       topo_msg.no_of_dead_units++ ;
  248.       if (topo_msg.src_error_unit == 0)
  249.         topo_msg.src_error_unit = unit_ptr - unit_array ;
  250.     }
  251.  
  252.   if (topo_msg.no_of_dead_units != 0)
  253.     KernelErrorCode = KRERR_DEAD_UNITS ;
  254.  
  255.   return (topo_msg.error_code) ;
  256. }
  257.  
  258.  
  259.  
  260. /*****************************************************************************
  261.   FUNCTION : kr_recTopoSortJE
  262.  
  263.   PURPOSE  : stores only hidden (NOT special hidden !) units in the topologic 
  264.              array
  265.   NOTES    : 
  266.  
  267.   RETURNS  : 
  268.   UPDATE   : 
  269. ******************************************************************************/
  270.  
  271. static void  kr_recTopoSortJE (struct Unit *unit_ptr, int depth)
  272.  
  273. {
  274.   struct Site   *site_ptr ;
  275.   struct Link   *link_ptr ;
  276.  
  277.  
  278.   /* ---------------------  ignore context units  ------------------------- */
  279.  
  280.   if ((IS_HIDDEN_UNIT (unit_ptr)) && (IS_SPECIAL_UNIT (unit_ptr)))
  281.   {
  282.     unit_ptr->flags |= UFLAG_REFRESH ;    /* set the 'touch' flag */
  283.     return ;
  284.   } 
  285.  
  286.  
  287.   if (unit_ptr->flags & UFLAG_REFRESH)
  288.   {  
  289.     /* the 'touch' flag is set: don't continue search */
  290.     topo_msg.src_error_unit = unit_ptr - unit_array ;  /* store unit number */
  291.  
  292.     if IS_OUTPUT_UNIT (unit_ptr)
  293.     {  
  294.       /*  this output unit has a output connection to another unit  */
  295.       if (topo_msg.error_code == KRERR_NO_ERROR)
  296.         topo_msg.error_code = KRERR_O_UNITS_CONNECT ;
  297.     }
  298.     else
  299.       if (unit_ptr->lln == 0)
  300.       {  
  301.         /*  logical layer no. isn't set => Cycle found  */
  302.           topo_msg.no_of_cycles++ ;
  303.         if (topo_msg.error_code == KRERR_NO_ERROR)
  304.           topo_msg.error_code = KRERR_CYCLES ;
  305.       }
  306.  
  307.     return ;
  308.   }
  309.   else
  310.     unit_ptr->flags |= UFLAG_REFRESH ; /* set the 'touch' flag */
  311.  
  312.  
  313.   /* -------------------------  continue search  -------------------------- */
  314.  
  315.   switch (unit_ptr->flags & UFLAG_INPUT_PAT)
  316.   {
  317.     case  UFLAG_DLINKS:   
  318.       FOR_ALL_LINKS (unit_ptr, link_ptr)
  319.     kr_recTopoSortJE (link_ptr->to, depth + 1) ; 
  320.       break ;
  321.  
  322.     case  UFLAG_SITES:    
  323.       FOR_ALL_SITES_AND_LINKS (unit_ptr, site_ptr, link_ptr)
  324.     kr_recTopoSortJE (link_ptr->to, depth + 1) ; 
  325.       break ;
  326.   }
  327.  
  328.   /*  remember the depth (for cycle detection and statistics)  */
  329.   unit_ptr->lln = depth ; 
  330.  
  331.  
  332.   /* ------------------------  store hidden units  ------------------------ */
  333.  
  334.   if IS_HIDDEN_UNIT( unit_ptr )
  335.   {
  336.     *topo_ptr++ = unit_ptr ; 
  337.     no_of_topo_units++ ;
  338.   }
  339. }
  340.  
  341.  
  342.  
  343. /*****************************************************************************
  344.   FUNCTION : kr_topoSortJE
  345.  
  346.   PURPOSE  : sorts units of a partial recurrent network by their topologic 
  347.              type input, hidden, output, context and stores the pointers to 
  348.              this units in the topologic array
  349.   NOTES    : ###########  V E R Y    I M P O R T A N T   N O T E  ############
  350.              no_of_topo_units contains only the number of input, hidden and
  351.              output units 
  352.  
  353.              no_of_topo_units DOES NOT contain the no. of context units !!!
  354.  
  355.              all special hidden units (io-type = SPECIAL_H) are assumed to
  356.              be context units 
  357.  
  358.              !! before calling this function:                  !!
  359.              !! check the network topology with kr_topoCheckJE !!
  360.  
  361.   RETURNS  : error code 
  362.   UPDATE   : 
  363. ******************************************************************************/
  364.  
  365. krui_err kr_topoSortJE (void)
  366.  
  367. { 
  368.   int i ;
  369.   register struct Unit     *unit_ptr ;
  370.  
  371.  
  372.   KernelErrorCode  = KRERR_NO_ERROR ;  /* reset return code                  */
  373.   topo_ptr         = topo_ptr_array ;  /* initialize global pointer          */
  374.   NoOfInputUnits   = 0 ;
  375.   NoOfOutputUnits  = 0 ;
  376.   no_of_topo_units = 0 ;
  377.   *topo_ptr++      = NULL ;            /* limit left side of the topological */
  378.                                        /* array with NULL pointer            */
  379.  
  380.  
  381.   /* ------------------  reset 'touch' flags of all units  ----------------- */
  382.  
  383.   FOR_ALL_UNITS (unit_ptr)
  384.     if (UNIT_IN_USE (unit_ptr))
  385.     {
  386.       unit_ptr->flags &= ~UFLAG_REFRESH ;
  387.       unit_ptr->lln = 0 ;
  388.     }
  389.  
  390.  
  391.   /* -----------  store all input units in the topologic array  ------------ */
  392.  
  393.   FOR_ALL_UNITS (unit_ptr)
  394.     if (IS_INPUT_UNIT (unit_ptr) && UNIT_IN_USE (unit_ptr))
  395.     {
  396.       if UNIT_HAS_INPUTS (unit_ptr)
  397.       { 
  398.         /* links to input units are not allowed */ 
  399.         topo_msg.dest_error_unit = unit_ptr - unit_array ;  
  400.     KernelErrorCode          = KRERR_I_UNITS_CONNECT ; 
  401.         return (KernelErrorCode) ;
  402.       }
  403.  
  404.       NoOfInputUnits++   ;    
  405.       no_of_topo_units++ ;    
  406.       *topo_ptr++ = unit_ptr ;  
  407.     }
  408.  
  409.   *topo_ptr++ = NULL ;  /* limit input units in the topological array with   */
  410.                         /* NULL pointer                                      */
  411.  
  412.   if (NoOfInputUnits == 0)
  413.   {  
  414.     KernelErrorCode = KRERR_NO_INPUT_UNITS ;
  415.     return( KernelErrorCode ) ;
  416.   }
  417.  
  418.  
  419.   /* -----------  store all hidden units in the topologic array  ----------- */
  420.   /* sorts hidden units by their topological order using recursive depth     */
  421.   /* search starting at the first output unit                                */
  422.  
  423.   FOR_ALL_UNITS( unit_ptr )
  424.     if (IS_OUTPUT_UNIT (unit_ptr) && UNIT_IN_USE (unit_ptr))
  425.     {
  426.       kr_recTopoSortJE (unit_ptr, 1) ;  
  427.       if (topo_msg.error_code != KRERR_NO_ERROR)
  428.       {  
  429.         KernelErrorCode = topo_msg.error_code ;
  430.         return (KernelErrorCode) ;
  431.       }
  432.     }
  433.  
  434.   *topo_ptr++ = NULL ;  /* limit hidden units in the topological array with  */
  435.                         /* NULL pointer                                      */
  436.  
  437.  
  438.   /* -----------  store all output units in the topologic array  ----------- */
  439.  
  440.   FOR_ALL_UNITS (unit_ptr)
  441.     if (IS_OUTPUT_UNIT (unit_ptr) && UNIT_IN_USE (unit_ptr))
  442.     {
  443.       NoOfOutputUnits++  ;    
  444.       no_of_topo_units++ ;
  445.       *topo_ptr++ = unit_ptr ;
  446.     }
  447.  
  448.   if (NoOfOutputUnits == 0)
  449.   { 
  450.     KernelErrorCode = KRERR_NO_OUTPUT_UNITS ;
  451.     return (KernelErrorCode) ;
  452.   }
  453.  
  454.   *topo_ptr++ = NULL ;  /* limit output units in the topological array with  */
  455.                         /* NULL pointer                                      */
  456.  
  457.  
  458.   /* ----------  store all context units in the topologic array  ----------- */
  459.   /*       !!!  no_of_topo_units MUST NOT BE INCREMENTED ANY MORE  !!!       */
  460.   
  461.   FOR_ALL_UNITS (unit_ptr)
  462.     if (IS_HIDDEN_UNIT (unit_ptr) && IS_SPECIAL_UNIT (unit_ptr) &&
  463.         UNIT_IN_USE (unit_ptr))
  464.     {
  465.       *topo_ptr++ = unit_ptr ;
  466.     }
  467.  
  468.   *topo_ptr++ = NULL ;  /* limit context units in the topological array with */
  469.                         /* NULL pointer                                      */
  470.  
  471.  
  472.   /* ---------  search for dead units i.e. units without inputs  ----------- */
  473.  
  474.   FOR_ALL_UNITS (unit_ptr)
  475.     if (!(unit_ptr->flags & UFLAG_REFRESH) && UNIT_IN_USE (unit_ptr))
  476.     {
  477.       topo_msg.no_of_dead_units++ ;
  478.       if (topo_msg.src_error_unit == 0)
  479.         topo_msg.src_error_unit = unit_ptr - unit_array ; 
  480.     }
  481.  
  482.   if (topo_msg.no_of_dead_units != 0) KernelErrorCode = KRERR_DEAD_UNITS ;
  483.  
  484.  
  485.   return( KernelErrorCode ) ;
  486. }
  487.  
  488.  
  489.  
  490. /*****************************************************************************
  491.                         E N D     O F     F I L E
  492. ******************************************************************************/
  493.  
  494.  
  495.  
  496.  
  497.